package com.berchen.数据结构.单链表;

/**
 * 约瑟夫问题 环形链表
 */
public class RingsLinketList {

    private Node first; // 第一个节点
    private Node end;   // 最后一个节点

    public boolean isEmpty(){
        return first==null;
    }

    /**
     * 往链表添加num个元素
     * @param num
     */
    public void add(int num){

        if(num<=0) throw new RuntimeException("数据错误");
        for (int i = 1; i <=num; i++) {
            Node node = new Node(i, "", "");
            if(isEmpty()){
                first=node;
                end=node;
                first.next=first;
            }else {
                end.next=node;
                node.next=first;
                end=node;
            }
        }
    }

    /**
     * 约瑟夫问题的出圈
     * @param k 开始计数从那个人开始报数  k-1 移动
     * @param m 报数多少  移动m-1
     */
    public void chuQun(int k,int m ){
        if(isEmpty()) throw new RuntimeException("链表为空");
        // 找到第一个开始报数的人
        for(int i=0;i<k-1;i++){
            first=first.next;
            end=end.next;
        }
        // 出圈
        while (true){
            if(first.next==first){
                break;
            }
            for(int i =0;i<m-1;i++){
                first=first.next;
                end=end.next;
            }
            // 出圈
            System.out.println(first);
            end.next=first.next;
            first=first.next;
        }
        System.out.println(first);
    }
}
